Background. Highly challenging exercises have been suggested to induce neuroplasticity in individuals with Parkinson’s disease (PD); however, its effect on clinical outcomes remains largely unknown. Objective. To evaluate the short-term effects of the HiBalance program, a highly challenging balance-training regimen that incorporates both dual-tasking and PD-specific balance components, compared with usual care in elderly with mild to moderate PD. Methods. Participants with PD (n = 100) were randomized, either to the 10-week HiBalance program (n = 51) or to the control group (n = 49). Participants were evaluated before and after the intervention. The main outcomes were balance performance (Mini-BESTest), gait velocity (during normal and dual-task gait), and concerns about falling (Falls Efficacy Scale–International). Performance of a cognitive task while walking, physical activity level (average steps per day), and activities of daily living were secondary outcomes. Results. A total of 91 participants completed the study. After the intervention, the between group comparison showed significantly improved balance and gait performance in the training group. Moreover, although no significant between group difference was observed regarding gait performance during dual-tasking; the participants in the training group improved their performance of the cognitive task while walking, as compared with the control group. Regarding physical activity levels and activities of daily living, in comparison to the control group, favorable results were found for the training group. No group differences were found for concerns about falling. Conclusions. The HiBalance program significantly benefited balance and gait abilities when compared with usual care and showed promising transfer effects to everyday living. Long-term follow-up assessments will further explore these effects.